//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 👍 4339 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //
    public String longestPalindrome(String s) {
        //状态转移方程：dp[i][j] = dp[i+1][j - 1]  && s[i][j]
        int len = s.length();
        if(len < 2 ){
            return s;
        }
        boolean[][] dp = new boolean[len][len];
        //一个字母的肯定是回文串
        for (int i = 0; i < len; i++){
            dp[i][i] = true;
        }
        char[] c = s.toCharArray();
        //寻找到的回文字符串最长长度
        int maxLen = 1;
        int start = 0;
        //一个字母的必为回文串，逐渐增加要寻找的回文串的长度，更新寻找到的最长回文串及起点
        //秒啊，递增地枚举子串长度，要判断长度为len的子串是否为回文串，只需要查询len-1的子串即可。
        //枚举子串长度
        for (int l = 2; l <= len; l++ )
            //枚举子串左起点
            for (int i = 0; i < len; i++){
                int j = i + l - 1;
                //如果右边界越界
                if(j >= len){
                    break;
                }
                //如果串两边字母不相等
            if(c[i] != c[j]){
                dp[i][j] = false;
            }else {
                //如果左右两边相等且长度小于3的子串为回文串
                if( j - i < 3){
                    dp[i][j] = true;
                }else {
                    dp[i][j] = dp[i+1][j-1];
                }
            }

            //如果长度超过maxLen，则更新起点和长度
            if(dp[i][j] && j - i + 1 > maxLen){
                maxLen = j - i + 1;
                start = i;
            }
        }
        return s.substring(start, start + maxLen);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
